#include<bits/stdc++.h>
using namespace std;
int t,n,a[100005][2],ans;
bool co[100005];
int dfs(int now,int color,int score){
    if(now>n) return score;
    bool check=true;
    int maxx=-1e9;
    if(a[now][1]==0){
        co[now]=0;
        maxx=max(maxx,dfs(now+1,co[now],score));
        co[now]=1;
        maxx=max(maxx,dfs(now+1,co[now],score));
    }else{
        for(int i=a[now][1]+1;i<now;i++){
            if(co[i]==co[a[now][1]]){
                check=false;
                break;
            }
        }
        if(check){
            co[now]=co[a[now][1]];
            maxx=max(maxx,dfs(now+1,co[now],score+a[now][0]));
            co[now]=co[a[now][1]]^1;
            maxx=max(maxx,dfs(now+1,co[now],score));
        }else{
            co[now]=0;
            maxx=max(maxx,dfs(now+1,co[now],score));
            co[now]=1;
            maxx=max(maxx,dfs(now+1,co[now],score));
        }
    }
    return maxx;
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        ans=-1e9;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i][0]);
            a[i][1]=0;
            for(int j=1;j<i;j++) if(a[i][0]==a[j][0]) a[i][1]=j;
        }
        co[1]=0;
        ans=max(ans,dfs(1,0,0));
        co[1]=1;
        ans=max(ans,dfs(1,1,0));
        printf("%d\n",ans);
    }
    return 0;
}
